package com.dq.offer;

import java.util.*;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/13  13:58
 * @Description:
 */
public class SortChar {
    public static void main(String[] args) {
        Solution solution = new SortChar().new Solution();
        String[] res = solution.permutation("abca");
        System.out.println(res.length);
        System.out.println(Arrays.toString(res));
    }

    class Solution {
        char[] c = null;
        Set<String> r = null;
        public String[] permutation(String s) {
            if(s==null || s.length()==0) return new String[]{};
            r = new HashSet<>();
            c = s.toCharArray();
            dfs(0);
            return r.toArray(new String[r.size()]);
        }
        private void dfs(int k){
            if(k == c.length-1){
                r.add(String.valueOf(c));
                return;
            }
            dfs(k+1);
            for(int i = k+1; i < c.length; i++){
                if(c[i] == c[k]) continue;
                swap(k, i);
                dfs(k+1);
                swap(k, i);
            }
        }
        private void swap(int i, int j){
            char temp = c[i];
            c[i] = c[j];
            c[j] = temp;
        }
    }
}
